You are given a collection $S$ of segments in the plane. Assume that no segment
is degenerate or horizontal, that no two segments are collinear, and that no two
segments intersect. Build a binary search tree using these segments as follows:
\begin{verbatim}
TreeBuild(S)
if |S|=0
    then tree T is a single node
    else select s uniformly at random from S
        /* denote by l(s) the line subtending s */
       	/* l(s) splits the current area and
       	may intersect remaining segments */
       	/* denote by l(s)- and l(s)+ the left and right half-planes,
       	not including the line l(s) itself */
       	let S+ contain the intersections of elements of S with l(s)+
       	/* note: each intersection is an intersection of geometric
       	objects -- a half-plane and a segment -- so the result
       	is a geometric object: a segment, a piece of a segment,
       	or nothing */
       	T+ <- TreeBuild(S+)
       	let S- contain the intersections of elements of S with l(s)-
       	T- <- TreeBuild(S-)
       	let T have s at the root, T- as left subtree, and T+ as right subtree
return T
\end{verbatim}

The tree leaves correspond to convex regions, each of which is empty of any
segment—all segments and segment pieces are on boundaries.
Analyze this algorithm in terms of both expected and worst-case running times.
(Hint: first derive the expected and worst-case number of pieces of segments
created by the splitting process, then use these values to bound the expected and
worst-case size of the tree, then finally analyze the running time.)

\vspace{10pt}

\textbf{Worst-case analysis}

	In the worst-case on the stage of splitting the line subtending chosen segment will intersect all others segments, producing $2 (n - 1)$ substeps. 
	We can construct the example where after each splitting at least at one subtree the segment choice can lead to the line intersecting all other segments.
	The construction of the example is represented on the figure beneath:
	
	\input{p3_figure.tex}
	
	So here the size of the tree will be $n + (n-1)+ \dots + 1 = \frac{n(n-1)}{2} = \Theta(n^2)$.
	This cannot be made worse as the number of all convex regions without segments is less than the number of intersections of lines subtending different segments, which is $\Theta(n^2)$.
	
	The running time of the algorithm then is $n$ times higher than the size of the tree, as at each vertex of a tree the algorithm needs to check the intersection of current constructed line with all remaining segments, which is $O(n)$. So overall algorithm will take $O(n^3)$ time.

\vspace{10pt}
\textbf{Average-case analysis}

	Suppose we have the set of segments $S = \{s_1, \dots, s_n\}$, for which we want to apply the described algorithm.
	
	Let's calculate the expected size of the constructed tree first.
	
	Suppose we have the random variable $I(i,j)$ equalled to $1$ if the line subtending the segment $s_i$ is intersecting the segment $s_j$, and $0$ otherwise. Then for each of this intersections the new node in the tree will be constructed in addition to the initial $n$ nodes for all segments. So the expected size of the tree is
	 $$\overline{\left| T\right| } = n + \mathsf{E}\left[ \sum_i \sum_j I(i,j)\right] = n + {\sum_i \sum_j \mathsf{E}  \left[ I(i,j) \right]}$$
	
	Let's notice that $I(i,j) = 1$, what means that  the line subtending the segment $s_i$ is intersecting the segment $s_j$, infer that the segment $s_i$ have to be chosen before the segment $j$ during the tree construction. Moreover, if the line subtending $s_i$ intersects the segments $s_{l_1}, s_{l_2}, \dots, s_{l_k}$ before intersecting the segment $s_j$, than the segment $s_i$ have to be chosen before any of those segments, which is by randomization can occur with probability $\frac{1}{k+2}$ (because the algorithm chose among $k+2$ segments which to put in the first place). Let's define the found number $k$ as $k(i,j)$ --- the number of segments which the line subtending the segment $s_i$ intersects before intersecting the segment $s_j$, not including $s_j$. Thus, in the defined terms for any $i$ and $j$:
	$$ \mathsf{E} \left[ I(i,j) \right] \le \frac{1}{k(i,j)+2}$$
	
	Then
	$$\sum_i \sum_j \mathsf{E} \left[ I(i,j)\right] \le \sum_i \sum_j \frac{1}{k(i,j)+2}$$ 
	
	Let's notice that for any segment $s_i$ when going in two different directions of the line subtending the segment $s_i$, we can construct two ordered lists of other segments in the order of intersections occurred (in the lists only intersected segments will be included). So at each list 
	the first segment $s_{j_1}$ have $k(i,j_1) = 0$, the following $s_{j_2}$ have on one more: $k(i,j_2) = 1$, and for the rest encountered segments it continues increasing, but cannot be more than $n-2$, as it is the case when all remaining segments are encountered. So for any $i$ the variable $k(i,j)$ can equal to the specified constant $c$ at most for two $j$, with the range of possible $c$ from $0$ to $n-2$. Then for any $i$
	
	 $$\sum_j \frac{1}{k(i,j)+2} \le \sum\limits_{c=0}^{n-2} \frac{2}{c+2} = \sum\limits_{c=1}^{n-1} \frac{2}{c+1}$$
	 
	 So if we substitute this estimation to the inequation above:
	 
	 $$\overline{\left| T\right| } \le n + \sum_i \sum_j \frac{1}{k(i,j)+2} \le n + \sum_i \sum\limits_{c=1}^{n-1} \frac{2}{c+1} \le n + 2 n H_n$$
	 
	 where $H_n = \sum\limits_{c=1}^{n} \frac{1}{n}$ is the harmonic number, which is $\Theta(\log n)$.
	 
	 Thus the expected size of the tree is $O(n \log n)$.
	 
	 The running time of the algorithm again is $n$ times higher than the size of the tree, as at each vertex of a tree the algorithm needs to check the intersection of current constructed line with all remaining segments, which is $O(n)$. So overall algorithm will take in expectation $O(n^2 \log n)$ time.